import java.util.*;

public class Solution {
    //JZ3 数组中重复的数字
    public int duplicate (int[] numbers) {
        //利用HashSet找出重复的数字,并返回
        if(numbers == null){
            return -1;
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < numbers.length; i++){
            if(set.contains(numbers[i])){
                return numbers[i];
            }else{
                set.add(numbers[i]);
            }
        }
        return -1;
    }
    //JZ51 数组中的逆序对(暴力求解，无法通过)
/*    public int InversePairs(int [] array) {
        //记录逆序个数
        int mod = 10_0000_0007;
        int count = 0;
        for(int cur = 1; cur < array.length; cur++){
            for(int prev = cur - 1; prev >= 0; prev--){
                if(array[prev] > array[cur]){
                    count++;
                    count %= mod;
                }
            }
        }
        return count;
    }*/
    //JZ40 最小的K个数
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> retArr = new ArrayList<>();
        if(k == 0){
            return retArr;
        }
        //top-k问题
        //建立大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        //先放入k个元素，再用数组后面的元素进行比较
        for(int i = 0; i < input.length; i++){
            if(i < k){
                queue.offer(input[i]);
            }else if(queue.peek() > input[i]){
                queue.offer(input[i]);
                queue.poll();
            }
        }
        //放入要返回的顺序表
        for(int i = 0; i < k; i++){
            retArr.add(queue.poll());
        }
        return retArr;
    }
    //JZ51 数组中的逆序对
    private int count = 0;
    public int InversePairs(int [] array) {
        if(array.length < 2){
            return 0;
        }
        //利用归并算法计算
        mergeFunc(array, 0, array.length - 1);
        return count;
    }
    private void mergeFunc(int[] array, int left, int right){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        mergeFunc(array, left, mid);
        mergeFunc(array, mid + 1, right);
        //合并
        merge(array, left, right, mid);
    }
    private void merge(int[] array, int start, int end, int mid){
        int[] tmpArr = new int[end - start + 1];
        int s1 = start;
        int s2 = mid + 1;
        //临时数组的下标
        int k = 0;
        while(s1 <= mid && s2 <= end){
            //发现逆序
            if(array[s1] > array[s2]){
                count += mid - s1 + 1;
                count %= 1000000007;
                //将小的加入临时数组
                tmpArr[k++] = array[s2++];
            }else{
                //不是逆序对，就可以将左数组放到临时数组
                tmpArr[k++] = array[s1++];
            }
        }
        while(s1 <= mid){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= end){
            tmpArr[k++] = array[s2++];
        }
        //合并
        for(int i = 0; i < tmpArr.length; i++){
            array[start + i] = tmpArr[i];
        }
    }
}
